package LeetCode.month02.day52;

import java.util.Arrays;
import java.util.Map;

public class No105 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right=new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        buildTree(new int[]{3,9,20,15,7},new int[]{9,3,15,20,7});
    }
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null||preorder.length==0) return null;
        TreeNode root = new TreeNode(preorder[0]);
        int inOrderRootIndex = -1;//中序中根节点位置
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i]==preorder[0]) {
                inOrderRootIndex = i;
                break;
            }
        }
        int inOrderLeftLast;
        int preOrderRightStartIndex;
        if(inOrderRootIndex==0){            //左子树为空
            root.left=null;
            preOrderRightStartIndex=1;
            if(preOrderRightStartIndex==preorder.length){
                root.right = null;
            }else{
                root.right = buildTree(Arrays.copyOfRange(preorder,preOrderRightStartIndex,preorder.length),Arrays.copyOfRange(inorder,inOrderRootIndex+1, inorder.length));
            }
        }else{                              //左子树非空
            inOrderLeftLast = inorder[inOrderRootIndex - 1];//左子树最后一个元素
            preOrderRightStartIndex = inOrderRootIndex+1; //右子树开始位置
            root.left = buildTree(Arrays.copyOfRange(preorder,1,preOrderRightStartIndex),Arrays.copyOfRange(inorder,0,inOrderRootIndex));
            if(preOrderRightStartIndex==preorder.length){
                root.right = null;
            }else{
                root.right = buildTree(Arrays.copyOfRange(preorder,preOrderRightStartIndex,preorder.length),Arrays.copyOfRange(inorder,inOrderRootIndex+1, inorder.length));
            }
        }
        return root;
    }
    /*
    index1 = Ar
    inorder[index1-1] 左子树最后一个元素
    preorder[]
     */
}
